/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/shortest-palindrome
   @Language: C++
   @Datetime: 19-06-17 09:59
   */

class Solution {
public:
	/**
	 * @param str: String
	 * @return: String
	 * KMP next
	 */
	string convertPalindrome(string &s) {
		// Write your code here
		int n=s.size();
		string rs(s);
		reverse(rs.begin(), rs.end());
		string srs = s+"#"+rs;
		vector<int> next(srs.size(), 0);
		for(int i=1, j; i<srs.size(); ++i){
			j = next[i-1];
			for(; j>0 && srs[i]!=srs[j]; j=next[j-1]);
			next[i] = j+(srs[i]==srs[j]);
		}
		return rs.substr(0, n-next.back())+s;
	}
};

